/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-09-18
 * Time: 15:18
 */

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}


public class demo2 {

    //除去链表中出现的元素
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        //
        while (head.val == val) {
            head = head.next;
            if (head == null) {
                return null;
            }
        }

        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null) {

            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;

        }

        return head;
    }


    //翻转链表
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode cur = head.next;
        ListNode next = null;
        head.next = null;
        while (cur != null) {

            next = cur.next;

            cur.next = head;
            head = cur;
            cur = next;
        }
        return head;
    }

    //返回中间结点
    public ListNode middleNode(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    //返回倒数第k个结点
    public int kthToLast(ListNode head, int k) {

        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k - 1; i++) {
            fast = fast.next;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

    //合并两个有序列表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode l1 = list1;
        ListNode l2 = list2;
        if (l1 == null && l2 == null) {
            return null;
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode newHead = new ListNode();

        if (l1.val >= l2.val) {
            newHead = l2;
            l2 = l2.next;
        } else {
            newHead = l1;
            l1 = l1.next;
        }
        ListNode cur = newHead;

        while (l1 != null && l2 != null) {
            if (l1.val >= l2.val) {
                cur.next = l2;
                l2 = l2.next;
                cur = cur.next;
            } else {
                cur.next = l1;
                l1 = l1.next;
                cur = cur.next;
            }
        }
        if (l1 == null) {
            cur.next = l2;
        }
        if (l2 == null) {
            cur.next = l1;
        }
        return newHead;
    }

    /**
     * 现有一链表的头指针 ListNode* pHead,
     * 给一定值x,编写一段代码将所有小于x的结点排在其余结点之前
     * 且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
     *
     * @param pHead
     * @param x
     * @return
     */
    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return null;
        }
        ListNode cur = pHead;//遍历链表
        ListNode preHead = null;//前半部分的头
        ListNode preTail = null;//前半部分的尾

        ListNode nextHead = null;//后半部分的头
        ListNode nextTail = null;//后半部分的尾

        while (cur != null) {
            //前
            if (cur.val < x) {
                //
                if (preHead == null) {
                    preHead = preTail = cur;
                } else {
                    preTail.next = cur;
                    preTail = preTail.next;
                }
                cur = cur.next;
            } else {
                //后
                if (nextHead == null) {
                    nextHead = nextTail = cur;
                } else {
                    nextTail.next = cur;
                    nextTail = nextTail.next;
                }
                cur = cur.next;
            }
        }
        //拼接
        if (preHead == null) {
            return nextHead;
        }
        preTail.next = nextHead;
        if (nextHead != null) {
            return nextTail.next = null;
        }
        return preHead;
    }
}
